home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / dict / _bb_tree1.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  18.4 KB  |  699 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _bb_tree1.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. //--------------------------------------------------------------------
  18. //  
  19. //  BB[alpha] Trees
  20. //
  21. //  Michael Wenzel   (1989)
  22. //
  23. // Implementation as described in
  24. // Kurt Mehlhorn: Data Structures and Algorithms 1, section III.5.1
  25. //
  26. // -------------------------------------------------------------------
  27. // Aenderungen:
  28. //   - keine virtuellen Funktionen  (M. Wenzel, Nov. 1989)
  29. //   - nicht rekursiv               (M. Wenzel, Nov. 1989)
  30. //   - virtuelle compare-Funktion   (M. Wenzel, Nov. 1989)
  31. //--------------------------------------------------------------------
  32.  
  33.  
  34.  
  35. #undef TEST
  36. #undef DUMP
  37.  
  38. #include <LEDA/impl/bb_tree1.h>
  39.  
  40. #ifdef TEST
  41. #define DPRINT(x) cout << string x
  42. #else
  43. #define DPRINT(x)   
  44. #endif
  45.  
  46. #ifdef DUMP
  47. #define DDUMP(x) cout << string x
  48. #else
  49. #define DDUMP(x)   
  50. #endif
  51.  
  52.  
  53.  
  54. enum children { left = 0 , right = 1 };
  55.  
  56. enum leaf_or_node { Leaf = 0 , Node = 1 } ;
  57.  
  58.  
  59. // -------------------------------------------------------------
  60. // member functions
  61. // -------------------------------------------------------------
  62.  
  63.  
  64.   bb_tree::bb_tree(float a)   : st(BSTACKSIZE)
  65.   { 
  66.     root = first = iterator = 0;
  67.     anzahl=0;
  68.     if ((a<=0.25) || (a>1-SQRT1_2))
  69.       error_handler(3,"alpha not in range");
  70.     alpha=a;
  71.     d = 1/(2-alpha) ;
  72.   }
  73.  
  74.   bb_tree::bb_tree(const bb_tree& w)  : st(BSTACKSIZE)
  75.   { 
  76.     bb_item p;
  77.     bb_item l=0;
  78.     anzahl=w.anzahl;
  79.     alpha=w.alpha;
  80.     d=w.d;
  81.     iterator=0;
  82.     if (w.root)
  83.     { if (!w.root->blatt())
  84.       { p=new bb_node(w.root);
  85.         first=copytree(p,w.root,l); 
  86.         first->sohn[left]=l;
  87.         l->sohn[right]=first; }
  88.       else
  89.       { p=new bb_node(w.root);
  90.         first=p; }
  91.       root= p;                      }
  92.     else root = 0;
  93.   }
  94.  
  95. // -------------------------------------------------------------
  96. // locate()
  97. // liefert item mit key(item) >= y und
  98. //              und key(it)   <= key(it) fuer alle it
  99. //                                          mit key(it) >= y
  100. //         0, falls nicht existiert
  101.  
  102. bb_item bb_tree::locate(GenPtr y)  const
  103.  
  104. { DPRINT(("locate %d in Baum %d\n",int(y),int(this)));
  105.   bb_item current;
  106.   if (root==0) return 0;  // by s.n
  107.   current=root;
  108.   while (!current->blatt())
  109.    { DDUMP(("current %d\n",int(current->key())));
  110.      if (cmp(y,current->key())<=0) current=current->sohn[left];
  111.      else current=current->sohn[right];   }
  112.   return (cmp(y,current->key())<=0) ? current : 0 ;
  113. }  
  114.  
  115. // -------------------------------------------------------------
  116. // located()
  117. // liefert item mit key(item) <= y und
  118. //              und key(it)   >= key(it) fuer alle it
  119. //                                       mit key(it) <= y
  120.  
  121. bb_item bb_tree::located(GenPtr y)  const
  122.  
  123. { bb_item current;
  124.   if (root==0) return 0;  // by s.n
  125.   current=root;
  126.   while (!current->blatt())
  127.    if (cmp(y,current->key())<=0) current=current->sohn[left];
  128.    else current=current->sohn[right];
  129.   if (cmp(y,current->key())==0) return current;
  130.   current = current->sohn[left];
  131.   return (cmp(y,current->key())>=0) ? current : 0 ;
  132. }  
  133.  
  134. // -------------------------------------------------------------
  135. // lookup()
  136. // liefert item mit key(item)=y , falls existiert
  137. //                            0 , sonst
  138.  
  139. bb_item bb_tree::lookup(GenPtr y) const
  140.  
  141. { bb_item current = locate(y);
  142.   if (current==0) return 0;
  143.   return (cmp(y,current->key())==0) ? current : 0;
  144. }  
  145.  
  146. // -------------------------------------------------------------  
  147. // member()
  148. // liefert 1 , falls item existiert mit key(item)=y
  149. //         0 , sonst
  150.  
  151. int bb_tree::member(GenPtr y)
  152.  
  153. { bb_item current = locate(y);
  154.   if (current==0) return 0;
  155.   return (cmp(y,current->key())==0);
  156. }  
  157.  
  158. // ------------------------------------------------------------
  159. // translate()
  160. // liefert info(item) , falls item existiert mit item = locate(y) 
  161. //                  0 , sonst
  162.  
  163. GenPtr bb_tree::translate(GenPtr y)
  164.  
  165. { bb_item current = locate(y);
  166.   if (current==0) return 0;
  167.   return (cmp(y,current->key())==0) ? current->inf : 0;
  168. }  
  169.  
  170. // ------------------------------------------------------------
  171. // change_obj()
  172. // liefert item mit key(item) = y und setzt info(item) auf x
  173. //                                    , falls existiert
  174. //         0                          , sonst
  175.  
  176. bb_item bb_tree::change_obj(GenPtr y,GenPtr x)
  177.  
  178. { bb_item current = lookup(y);
  179.   if ( current != 0 )
  180.   { current->inf = x ;  
  181.     return current; }
  182.   else return 0;
  183. }  
  184.  
  185. // ------------------------------------------------------------
  186. // search()
  187. // nachher: st = ( pk ,..., p1 ) mit 
  188. //          pk = locate(y) , p1 = root 
  189. //          p1 , ... , pk ist Suchpfad nach y
  190. // liefert inneren Knoten k mit key(k) = y , falls existiert
  191. //         0                               , sonst
  192.  
  193. bb_item bb_tree::search(GenPtr y)
  194.  
  195. { DPRINT(("search %d in Baum %d\n",int(y),int(this)));
  196.   st.clear();
  197.   bb_item current = root;
  198.   bb_item k = 0;
  199.  
  200.   if (!root) return 0;         // Baum leer
  201.   while (!current->blatt())
  202.   { DDUMP(("current %d\n",int(current->key())));
  203.     if (cmp(y,current->key())<=0)
  204.     { if (cmp(y,current->key())==0) k=current;
  205.       st.push(current);
  206.       current = current->sohn[left];          }
  207.     else
  208.     { st.push(current);
  209.       current = current->sohn[right];         }
  210.                            }
  211.   st.push(current);
  212.   DDUMP(("Blatt %d\n",int(current->key())));
  213.   return k;
  214. }
  215.  
  216. // -----------------------------------------------------------
  217. // ord()
  218. // liefert item it mit
  219. //              |{key(it') < key(it) | it' item im Baum}| = k-1
  220. //         0 , falls kein solches item existiert
  221.     
  222. bb_item bb_tree::ord(int k)
  223.  
  224. { DPRINT(("ord %d\n",k));
  225.   if (k>anzahl || k<=0) return 0;
  226.   bb_item cur=root;
  227.   while (!cur->blatt())
  228.   { DDUMP(("ord loop k=%d key=%d\n",k,int(cur->key())));
  229.     int l=cur->sohn[left]->groesse();
  230.     if (k>l)
  231.     { k -= l;
  232.       cur=cur->sohn[right];           }
  233.     else cur=cur->sohn[left]; 
  234.   }
  235.   return cur;
  236. }
  237.     
  238. // ------------------------------------------------------------
  239. // move_iterator()
  240. // bewegt Iterator eine Stelle weiter
  241. // falls am Ende , Iterator = 0
  242.  
  243. bb_item bb_tree::move_iterator()
  244.  
  245.   { 
  246.     if (!root) 
  247.     { iterator = 0;
  248.       return 0;      }
  249.     
  250.     if (!iterator) iterator = first;
  251.     else if (iterator->sohn[right]==first) iterator = 0;
  252.      else iterator = iterator->sohn[right];
  253.     return iterator;
  254.   }
  255.     
  256. // ------------------------------------------------------------
  257. // lrot() , rrot() , ldrot() , rdrot()
  258. // Rotationen am Knoten p
  259.  
  260. void bb_tree::lrot(bb_item p, bb_item q)
  261. { DDUMP(("lrot p=%d \n",int(p->key())));
  262.   bb_item h = p->sohn[right];
  263.   p->sohn[right] = h->sohn[left];
  264.   h->sohn[left] = p;
  265.   if (!q) root=h;
  266.   else
  267.     if (cmp(p->key(),q->key())>0) q->sohn[right]=h;
  268.     else q->sohn[left]=h;
  269.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  270.   h->gr=p->groesse()+h->sohn[right]->groesse();
  271. }
  272.  
  273. void bb_tree::rrot(bb_item p, bb_item q)
  274. { DDUMP(("rrot p=%d\n",int(p->key())));
  275.   bb_item h = p->sohn[left];
  276.   p->sohn[left] = h->sohn[right];
  277.   h->sohn[right] = p;
  278.   if (!q) root=h;
  279.   else
  280.   { if (cmp(p->key(),q->key())>0) q->sohn[right] = h;
  281.     else q->sohn[left] = h; }
  282.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  283.   h->gr=p->groesse()+h->sohn[left]->groesse();
  284. }
  285.  
  286. void bb_tree::ldrot(bb_item p, bb_item q)
  287. { DDUMP(("ldrot p=%d\n",int(p->key())));
  288.   bb_item h = p->sohn[right];
  289.   bb_item g = h->sohn[left];
  290.   p->sohn[right] = g->sohn[left];
  291.   h->sohn[left] =  g->sohn[right];
  292.   g->sohn[left] = p;
  293.   g->sohn[right] = h;
  294.   if (!q) root=g;
  295.   else
  296.   { if (cmp(p->key(),q->key())>0) q->sohn[right] =g ;
  297.     else q->sohn[left] = g ; }
  298.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  299.   h->gr=h->sohn[left]->groesse()+h->sohn[right]->groesse();
  300.   g->gr=p->groesse()+h->groesse();
  301. }
  302.  
  303. void bb_tree::rdrot(bb_item p, bb_item q)
  304. { DDUMP(("rdrot p=%d\n",int(p->key())));
  305.   bb_item h = p->sohn[left];
  306.   bb_item g = h->sohn[right];
  307.   p->sohn[left] = g->sohn[right];
  308.   h->sohn[right] =  g->sohn[left];
  309.   g->sohn[right] = p;
  310.   g->sohn[left] = h;
  311.   if (!q) root=g;
  312.   else
  313.   { if (cmp(p->key(),q->key())>0) q->sohn[right] =g ;
  314.     else q->sohn[left] = g ; }
  315.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  316.   h->gr=h->sohn[left]->groesse()+h->sohn[right]->groesse();
  317.   g->gr=p->groesse()+h->groesse();
  318. }
  319.  
  320. // ------------------------------------------------------------------
  321. // sinsert()
  322. // fuegt ein neues Item (y,x) in den Baum ein
  323. //                 , falls noch kein Item it vorhanden mit key(it)=y
  324. // change_obj(y,x) ,sonst
  325. // fuellt Keller mit zu rebalancierenden Knoten 
  326. // gibt eingefuegtes Blatt zurueck
  327.  
  328.       bb_item bb_tree::sinsert(GenPtr y,GenPtr x=0)
  329.       { DPRINT(("sinsert %d [%d] in Baum %d\n",int(y),int(x),int(this)));
  330.     bb_item inserted;
  331.     bb_item help;
  332.  
  333.     if (!alpha) error_handler(5,"alpha nicht gesetzt");
  334.     if (iterator)  error_handler(6,"insert while tree listed");
  335.  
  336.     st.clear();                           // loesche Suchpfad
  337.  
  338.     if (!root) { DDUMP(("Baum war leer\n"));
  339.              bb_item p=new  bb_node(y,x);
  340.              p->sohn[left]=p;
  341.              p->sohn[right]=p;
  342.              root=p; 
  343.              first=p;
  344.              first->sohn[left]=first;
  345.              first->sohn[right]=first;
  346.              anzahl=1; 
  347.              inserted = p;
  348.            }
  349.     else
  350.       if (root->blatt())
  351.         if (cmp(y,root->key())<0)
  352.         { DDUMP(("links von Wurzel\n"));
  353.           bb_item p=new bb_node(y,x,Leaf,root,root);
  354.           DDUMP(("Blatt[%d] %d %d %d %d\n",(int)p,(int)p->key(),(int)p->info(),(int)p->sohn[left],(int)p->sohn[right]));
  355.           root->sohn[left]=p;
  356.           root->sohn[right]=p;
  357.           bb_item s=new bb_node(y,x,Node,p,root);
  358.           DDUMP(("Knoten[%d] %d %d %d %d\n",(int)s,(int)s->key(),(int)s->info(),(int)s->sohn[left],(int)s->sohn[right]));
  359.           first=p;
  360.           root=s;
  361.           st.push(s);
  362.           anzahl++; 
  363.           inserted = p;
  364.          }
  365.         else if (cmp(y,root->key())>0)         // hier rechts einfuegen
  366.          { DDUMP(("rechts von Wurzel\n"));
  367.            bb_item p=new bb_node(y,x,Leaf,root,root);
  368.            root->sohn[left]=p;
  369.            root->sohn[right]=p;
  370.            bb_item s=new bb_node(root->key(),root->inf,Node,root,p);
  371.            root=s;
  372.            st.push(s);
  373.            anzahl++;
  374.            inserted = p;
  375.           }
  376.          else { DPRINT(("gleicher Schluessel vorhanden\n"));
  377.             root->inf = x;
  378.             inserted = root;
  379.                }
  380.       else                           // root ist innerer Knoten
  381.       { bb_item father;
  382.         search(y);                   // fuelle Suchstack 
  383.         bb_item t=st.pop();
  384.         father = st.top();
  385.                      // einfuegen
  386.         if (cmp(y,t->key())<0)
  387.         { DDUMP(("insert links von Blatt\n"));
  388.           help = t->sohn[left];
  389.           bb_item  p = new bb_node(y,x,Leaf,help,t);
  390.           t->sohn[left]=p;
  391.           if (first==t) first=p;
  392.           help->sohn[right]=p;
  393.           bb_item s=new bb_node(y,x,Node,p,t);
  394.           if (cmp(s->key(),father->key())<=0) father->sohn[left]=s;
  395.           else father->sohn[right]=s;
  396.           anzahl++; 
  397.           inserted = p;
  398.           st.push(s);
  399.         }
  400.         else if (cmp(y,t->key())>0)     
  401.          { DDUMP(("insert rechts von Blatt -> neues Maximum\n"));
  402.            help=t->sohn[right];
  403.            bb_item p=new bb_node(y,x,Leaf,t,help);
  404.            t->sohn[right]=p;
  405.            help->sohn[left]=p;
  406.            bb_item s=new bb_node(t->key(),t->inf,Node,t,p);
  407.  
  408.            father->sohn[right] = s;
  409.            anzahl++;
  410.            inserted = p;
  411.            st.push(s);
  412.          }
  413.          else { DPRINT(("gleicher Schluessel vorhanden\n"));
  414.             t->inf = x;
  415.             st.clear();     // keine Rebalancierung notwendig
  416.             inserted = t;
  417.               }
  418.       }
  419.       return inserted;
  420.       }
  421.  
  422.  
  423. // ------------------------------------------------------------------
  424. // insert()
  425. // fuegt ein neues Item (y,x) in den Baum ein
  426. //       mittels sinsert
  427. // balanciert Baum mit ueblichen Rotationen
  428. // gibt eingefuegtes Blatt zurueck
  429.  
  430. bb_item bb_tree::insert(GenPtr y, GenPtr x)
  431. { 
  432.   bb_item inserted;
  433.   bb_item t,father;
  434.  
  435. /*
  436.   copy_key(y);
  437.   copy_inf(x);
  438. */
  439.  
  440.   inserted = sinsert(y,x);
  441.   if (!st.empty())
  442.     st.pop();                       // pop father of leaf
  443.   
  444.                     // rebalancieren
  445.   while (!st.empty())
  446.   { t=st.pop();
  447.     father = st.empty() ? 0 : st.top();
  448.     t->gr++;  
  449.     float i = t->bal();
  450.     DDUMP(("rebal cur=%d groesse=%d bal=%f\n",int(t->key()),t->groesse(),i));
  451.     if (i < alpha)
  452.       if (t->sohn[right]->bal()<=d) lrot(t,father);
  453.       else ldrot(t,father);
  454.     else if (i>1-alpha) 
  455.            if (t->sohn[left]->bal() > d ) rrot(t,father);
  456.        else rdrot(t,father);
  457.   }
  458.   DDUMP(("eingefuegtes Blatt hat key %d und info %d\n",int(inserted->key()),int(inserted->info())));
  459.   return inserted;
  460. }
  461.  
  462. // ------------------------------------------------------------------
  463. // sdel()
  464. // loescht Item it im Baum mit key(it)=y , falls existiert
  465. //         und gibt Zeiger auf it zurueck
  466. // 0 , sonst
  467. // fuellt Keller mit zu rebalancierenden Knoten
  468.  
  469. bb_item bb_tree::sdel(GenPtr y)
  470. { DPRINT(("delete %d aus Baum %d\n",int(y),int(this)));
  471.  
  472.   if (!alpha) error_handler(5,"alpha nicht gesetzt");
  473.   if (iterator)  error_handler(6,"Baum gelistet beim Loeschen");
  474.  
  475.   st.clear();
  476.   if (root==0) return 0;                         // s.n.
  477.  
  478.   if (root->blatt())                             // Wurzel loeschen
  479.     if (cmp(y,root->key())==0)
  480.       { DDUMP(("Wurzel loeschen\n"));
  481.         bb_item p = root;
  482.         first=iterator=0;
  483.         anzahl=0; 
  484.         root=0; 
  485.         return p; 
  486.        }
  487.     else 
  488.       { DPRINT(("Element nicht im Baum\n"));  
  489.         return 0; }
  490.   else 
  491.   { bb_item p,father;
  492.     bb_item pp=search(y);
  493.  
  494.     if (st.size()==2)                            // Sohn der Wurzel
  495.     { DDUMP(("Sohn der Wurzel loeschen\n"));
  496.       p=st.pop();
  497.       father=st.pop();
  498.  
  499.       int v1 = cmp(y,father->key());
  500.       if (cmp(y,p->key())!=0) { DPRINT(("Element nicht im Baum\n"));
  501.                                 return 0; }
  502.       anzahl--;
  503.  
  504.       if (v1<=0)
  505.         root=root->sohn[right];
  506.       else
  507.         root=root->sohn[left];
  508.  
  509.       if (!root->blatt())
  510.        { if (first==p) first=p->sohn[right];
  511.          first->sohn[left]=p->sohn[left];
  512.          (first->sohn[left])->sohn[right]=first;
  513.         }
  514.       else
  515.        { first=root;
  516.          root->sohn[left]=root;
  517.          root->sohn[right]=root ;
  518.         }
  519.  
  520.       st.push(father);
  521.       return p; 
  522.     }
  523.     else                                // Blatt mit Tiefe >= 2     
  524.     { bb_item q=st.pop();
  525.  
  526.       if (cmp(y,q->key())!=0)
  527.       { DDUMP(("Schluessel nicht vorhanden\n"));
  528.     return 0;   }
  529.  
  530.       bb_item p = st.pop();
  531.       father=st.top();
  532.       DDUMP(("Blatt %d mit Vater %d , Grossvater %d\n",int(q->key()),int(p->key()),int(father->key())));
  533.       int v2 = cmp(y,p->key());
  534.       int v1 = cmp(y,father->key());
  535.       anzahl--;
  536.       if (v1<=0)
  537.         if (v2<=0)
  538.         { father->sohn[left]=p->sohn[right];
  539.           if (first==q) { first=first->sohn[right];
  540.               q->sohn[right]->sohn[left]=first; }
  541.     }
  542.         else father->sohn[left]=p->sohn[left];
  543.       else if (v2<=0) father->sohn[right]=p->sohn[right];
  544.            else  father->sohn[right]=p->sohn[left];
  545.       q->sohn[right]->sohn[left]=q->sohn[left];
  546.       q->sohn[left]->sohn[right]=q->sohn[right];
  547.       if ( pp && (p!=pp) && p->sohn[left] )
  548.       { pp->ke = q->sohn[left]->key() ;
  549.         DPRINT(("inneren Knoten mit %d ueberschrieben und Info %d bleibt\n",int(pp->key()),int(pp->info())));
  550.       }
  551.       st.push(p);
  552.       return q;
  553.     }
  554.   }
  555. #if defined(__GNUG__)
  556.   return 0; // never reached ?
  557. #endif
  558. }
  559.  
  560. // ------------------------------------------------------------------
  561. // del()
  562. // loescht Item it im Baum mit key(it)=y , falls existiert
  563. //         und gibt Zeiger auf it zurueck
  564. // 0 , sonst
  565. // mittels sdel                                     
  566. // rebalanciert Baum danach
  567.  
  568. bb_item bb_tree::del(GenPtr y)
  569. {
  570.   bb_item p,father;
  571.   bb_item deleted = sdel(y);
  572.   if (!deleted)
  573.     return 0;
  574.   if (!st.empty())
  575.     delete(st.pop());
  576.  
  577.                      // rebalancieren
  578.   while (!st.empty())
  579.   { p = st.pop();
  580.     father = st.empty() ? 0 : st.top() ;
  581.     p->gr--;              
  582.     float i=p->bal();
  583.     DDUMP(("rebal cur=%d groesse=%d bal=%f\n",int(p->key()),p->groesse(),i));
  584.     if (i<alpha)
  585.       if (p->sohn[right]->bal() <= d) lrot(p,father);
  586.       else ldrot(p,father);
  587.     else if (i>1-alpha)
  588.            if(p->sohn[left]->bal() > d) rrot(p,father);
  589.            else rdrot(p,father);
  590.   }
  591.   return deleted;
  592. } 
  593.  
  594. // -----------------------------------------------------------------
  595. // Gleichheitsoperator
  596. // weist this Kopie der Baumes w zu
  597.  
  598. bb_tree& bb_tree::operator=(const bb_tree& w)
  599. { DDUMP(("operator = wurzel%d\n",(int)w.root->key()));
  600.   bb_item p;
  601.   bb_item l=0;
  602.   if (anzahl!=0) deltree(root); 
  603.   st.clear();
  604.   anzahl=w.anzahl;
  605.   alpha=w.alpha;
  606.   d=w.d;
  607.   iterator=0;
  608.   if (w.root)
  609.   { if (!w.root->blatt())
  610.     { p=new bb_node(w.root);
  611.       first=copytree(p,w.root,l);
  612.       first->sohn[left]=l ;
  613.       l->sohn[right]=first ; }
  614.     else
  615.     { p=new bb_node(w.root);
  616.       first=p; }
  617.     root= p;                       }
  618.   else root = 0;
  619.   DDUMP(("root=%d, first=%d\n",int(root->key()),int(first->key())));
  620.   return *this;
  621. }
  622.  
  623. bb_item bb_tree::copytree(bb_item p, bb_item q,bb_item& ll) 
  624. { DDUMP(("copytree %d\n",(int)p->key()));
  625.   bb_item a;
  626.   bb_item r;
  627.   bb_item s;
  628.   if (p->blatt())
  629.   { if (ll==0) p->sohn[left]=0;
  630.     else
  631.     { p->sohn[left]=ll;
  632.       ll->sohn[right]=p; }
  633.     p->sohn[right]=0;
  634.     a=p;
  635.     ll=p; 
  636.     DDUMP(("ll gesetzt %d\n",int(ll->key()))); }
  637.   else {
  638.     r=new bb_node(q->sohn[left]);
  639.     p->sohn[left]=r;
  640.     a=copytree(p->sohn[left],q->sohn[left],ll);
  641.     s=new bb_node(q->sohn[right]);
  642.     p->sohn[right]=s;
  643.     copytree(p->sohn[right],q->sohn[right],ll); }
  644.   return a; 
  645. }
  646.  
  647. // ------------------------------------------------------------------
  648. // Destruktoren
  649.  
  650. void bb_tree::clear()
  651. { if (root)
  652.   { DPRINT(("clear %d\n",int(root->key())));
  653.     deltree(root);
  654.    }
  655.   else DPRINT(("clear\n"));
  656.   root=0;
  657.   anzahl=0;
  658.   first=0;
  659. }
  660.  
  661. void bb_tree::deltree(bb_item p)
  662. { if (p)
  663.   { DDUMP(("deltree : current=%d\n",int(p->key())));
  664.     if (!p->blatt())
  665.     {  deltree(p->sohn[left]);
  666.        deltree(p->sohn[right]); 
  667.      }
  668.     delete(p);
  669.   }
  670. }
  671.  
  672.  
  673. void bb_tree::draw(DRAW_BB_NODE_FCT draw_node,
  674.                    DRAW_BB_EDGE_FCT draw_edge, 
  675.                    bb_node* r, 
  676.                    double x1, double x2, double y, 
  677.                    double ydist, double last_x)
  678. { 
  679.  double x = (x1+x2)/2;
  680.  
  681.  if (r==nil) return;
  682.  
  683.  if (last_x != 0) draw_edge(last_x,y+ydist,x,y);
  684.  
  685.  draw_node(x,y,r->key());
  686.  
  687.  if (!r->blatt()) 
  688.  { draw(draw_node,draw_edge,r->sohn[0],x1,x,y-ydist,ydist,x);
  689.    draw(draw_node,draw_edge,r->sohn[1],x,x2,y-ydist,ydist,x);
  690.   }
  691. }
  692.  
  693.  
  694. void bb_tree::draw(DRAW_BB_NODE_FCT draw_node,
  695.                    DRAW_BB_EDGE_FCT draw_edge, 
  696.                    double x1, double x2, double y, double ydist)
  697. { draw(draw_node,draw_edge,root,x1,x2,y,ydist,0); }
  698.  
  699.